home *** CD-ROM | disk | FTP | other *** search
/ Apple Developer Connection Student Program / ADC Tools Sampler CD Disk 3 1999.iso / Metrowerks CodeWarrior / Java Support / Java_Source / Java2 / src / java / util / HashSet.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  8.3 KB  |  251 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)HashSet.java    1.14 98/09/30
  3.  *
  4.  * Copyright 1997, 1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. /**
  18.  * This class implements the <tt>Set</tt> interface, backed by a hash table
  19.  * (actually a <tt>HashMap</tt> instance).  It makes no guarantees as to the
  20.  * iteration order of the set; in particular, it does not guarantee that the
  21.  * order will remain constant over time.  This class permits the <tt>null</tt>
  22.  * element.<p>
  23.  *
  24.  * This class offers constant time performance for the basic operations
  25.  * (<tt>add</tt>, <tt>remove</tt>, <tt>contains</tt> and <tt>size</tt>),
  26.  * assuming the hash function disperses the elements properly among the
  27.  * buckets.  Iterating over this set requires time proportional to the sum of
  28.  * the <tt>HashSet</tt> instance's size (the number of elements) plus the
  29.  * "capacity" of the backing <tt>HashMap</tt> instance (the number of
  30.  * buckets).  Thus, it's very important not to set the intial capacity too
  31.  * high (or the load factor too low) if iteration performance is important.<p>
  32.  *
  33.  * <b>Note that this implementation is not synchronized.</b> If multiple
  34.  * threads access a set concurrently, and at least one of the threads modifies
  35.  * the set, it <i>must</i> be synchronized externally.  This is typically
  36.  * accomplished by synchronizing on some object that naturally encapsulates
  37.  * the set.  If no such object exists, the set should be "wrapped" using the
  38.  * <tt>Collections.synchronizedSet</tt> method.  This is best done at creation
  39.  * time, to prevent accidental unsynchronized access to the <tt>HashSet</tt>
  40.  * instance:
  41.  * 
  42.  * <pre>
  43.  *     Set s = Collections.synchronizedSet(new HashSet(...));
  44.  * </pre><p>
  45.  *
  46.  * The iterators returned by this class's <tt>iterator</tt> method are
  47.  * <i>fail-fast</i>: if the set is modified at any time after the iterator is
  48.  * created, in any way except through the iterator's own <tt>remove</tt>
  49.  * method, the Iterator throws a <tt>ConcurrentModificationException</tt>.
  50.  * Thus, in the face of concurrent modification, the iterator fails quickly
  51.  * and cleanly, rather than risking arbitrary, non-deterministic behavior at
  52.  * an undetermined time in the future.
  53.  * 
  54.  * @author  Josh Bloch
  55.  * @version 1.14 09/30/98
  56.  * @see        Collection
  57.  * @see        Set
  58.  * @see        TreeSet
  59.  * @see        Collections#synchronizedSet(Set)
  60.  * @see        HashMap
  61.  * @since JDK1.2
  62.  */
  63.  
  64. public class HashSet extends AbstractSet
  65.              implements Set, Cloneable, java.io.Serializable
  66. {
  67.     private transient HashMap map;
  68.  
  69.     // Dummy value to associate with an Object in the backing Map
  70.     private static final Object PRESENT = new Object();
  71.  
  72.     /**
  73.      * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
  74.      * default capacity and load factor, which is <tt>0.75</tt>.
  75.      */
  76.     public HashSet() {
  77.     map = new HashMap();
  78.     }
  79.  
  80.     /**
  81.      * Constructs a new set containing the elements in the specified
  82.      * collection.  The capacity of the backing <tt>HashMap</tt> instance is
  83.      * twice the size of the specified collection or eleven (whichever is
  84.      * greater), and the default load factor (which is <tt>0.75</tt>) is used.
  85.      */
  86.     public HashSet(Collection c) {
  87.     map = new HashMap(Math.max(2*c.size(), 11));
  88.     addAll(c);
  89.     }
  90.  
  91.     /**
  92.      * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
  93.      * the specified initial capacity and the specified load factor.
  94.      *
  95.      * @param      initialCapacity   the initial capacity of the hash map.
  96.      * @param      loadFactor        the load factor of the hash map.
  97.      * @throws     IllegalArgumentException if the initial capacity is less
  98.      *             than zero, or if the load factor is nonpositive.
  99.      */
  100.     public HashSet(int initialCapacity, float loadFactor) {
  101.     map = new HashMap(initialCapacity, loadFactor);
  102.     }
  103.  
  104.     /**
  105.      * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
  106.      * the specified initial capacity and default load factor, which is
  107.      * <tt>0.75</tt>.
  108.      *
  109.      * @param      initialCapacity   the initial capacity of the hash table.
  110.      * @throws     IllegalArgumentException if the initial capacity is less
  111.      *             than zero.
  112.      */
  113.     public HashSet(int initialCapacity) {
  114.     map = new HashMap(initialCapacity);
  115.     }
  116.  
  117.     /**
  118.      * Returns an iterator over the elements in this set.  The elements
  119.      * are returned in no particular order.
  120.      *
  121.      * @return an Iterator over the elements in this set.
  122.      * @see ConcurrentModificationException
  123.      */
  124.     public Iterator iterator() {
  125.     return map.keySet().iterator();
  126.     }
  127.  
  128.     /**
  129.      * Returns the number of elements in this set (its cardinality).
  130.      *
  131.      * @return the number of elements in this set (its cardinality).
  132.      */
  133.     public int size() {
  134.     return map.size();
  135.     }
  136.  
  137.     /**
  138.      * Returns <tt>true</tt> if this set contains no elements.
  139.      *
  140.      * @return <tt>true</tt> if this set contains no elements.
  141.      */
  142.     public boolean isEmpty() {
  143.     return map.isEmpty();
  144.     }
  145.  
  146.     /**
  147.      * Returns <tt>true</tt> if this set contains the specified element.
  148.      *
  149.      * @return <tt>true</tt> if this set contains the specified element.
  150.      */
  151.     public boolean contains(Object o) {
  152.     return map.containsKey(o);
  153.     }
  154.  
  155.     /**
  156.      * Adds the specified element to this set if it is not already
  157.      * present.
  158.      *
  159.      * @param o element to be added to this set.
  160.      * @return <tt>true</tt> if the set did not already contain the specified
  161.      * element.
  162.      */
  163.     public boolean add(Object o) {
  164.     return map.put(o, PRESENT)==null;
  165.     }
  166.  
  167.     /**
  168.      * Removes the given element from this set if it is present.
  169.      *
  170.      * @param o object to be removed from this set, if present.
  171.      * @return <tt>true</tt> if the set contained the specified element.
  172.      */
  173.     public boolean remove(Object o) {
  174.     return map.remove(o)==PRESENT;
  175.     }
  176.  
  177.     /**
  178.      * Removes all of the elements from this set.
  179.      */
  180.     public void clear() {
  181.     map.clear();
  182.     }
  183.  
  184.     /**
  185.      * Returns a shallow copy of this <tt>HashSet</tt> instance: the elements
  186.      * themselves are not cloned.
  187.      *
  188.      * @return a shallow copy of this set.
  189.      */
  190.     public Object clone() {
  191.     try { 
  192.         HashSet newSet = (HashSet)super.clone();
  193.         newSet.map = (HashMap)map.clone();
  194.         return newSet;
  195.     } catch (CloneNotSupportedException e) { 
  196.         throw new InternalError();
  197.     }
  198.     }
  199.  
  200.     /**
  201.      * Save the state of this <tt>HashSet</tt> instance to a stream (that is,
  202.      * serialize this set).
  203.      *
  204.      * @serialData The capacity of the backing <tt>HashMap</tt> instance
  205.      *           (int), and its load factor (float) are emitted, followed by
  206.      *           the size of the set (the number of elements it contains)
  207.      *           (int), followed by all of its elements (each an Object) in
  208.      *             no particular order.
  209.      */
  210.     private synchronized void writeObject(java.io.ObjectOutputStream s)
  211.         throws java.io.IOException {
  212.     // Write out any hidden serialization magic
  213.     s.defaultWriteObject();
  214.  
  215.         // Write out HashMap capacity and load factor
  216.         s.writeInt(map.capacity());
  217.         s.writeFloat(map.loadFactor());
  218.  
  219.         // Write out size
  220.         s.writeInt(map.size());
  221.  
  222.     // Write out all elements in the proper order.
  223.     for (Iterator i=map.keySet().iterator(); i.hasNext(); )
  224.             s.writeObject(i.next());
  225.     }
  226.  
  227.     /**
  228.      * Reconstitute the <tt>HashSet</tt> instance from a stream (that is,
  229.      * deserialize it).
  230.      */
  231.     private synchronized void readObject(java.io.ObjectInputStream s)
  232.         throws java.io.IOException, ClassNotFoundException {
  233.     // Read in any hidden serialization magic
  234.     s.defaultReadObject();
  235.  
  236.         // Read in HashMap capacity and load factor and create backing HashMap
  237.         int capacity = s.readInt();
  238.         float loadFactor = s.readFloat();
  239.         map = new HashMap(capacity, loadFactor);
  240.  
  241.         // Read in size
  242.         int size = s.readInt();
  243.  
  244.     // Read in all elements in the proper order.
  245.     for (int i=0; i<size; i++) {
  246.             Object e = s.readObject();
  247.             map.put(e, PRESENT);
  248.         }
  249.     }
  250. }
  251.